package person.bing.fbcloud.leetcode;

import java.util.Arrays;

/**
 * 面试题 17.13. 恢复空格
 *
 * @author: mengfanbing
 * @date: 2020/7/9 9:51
 */
public class RespaceMethod {
    public static void main(String[] args) {
        String[] dictionary = {"aaysaayayaasyya","yyas","yayysaaayasasssy","yaasassssssayaassyaayaayaasssasysssaaayysaaasaysyaasaaaaaasayaayayysasaaaa","aya","sya","ysasasy","syaaaa","aaaas","ysa","a","aasyaaassyaayaayaasyayaa","ssaayayyssyaayyysyayaasaaa","aya","aaasaay","aaaa","ayyyayssaasasysaasaaayassasysaaayaassyysyaysaayyasayaaysyyaasasasaayyasasyaaaasysasy","aaasa","ysayssyasyyaaasyaaaayaaaaaaaaassaaa","aasayaaaayssayyaayaaaaayaaays","s"};
        String sentence = "asasayaayaassayyayyyyssyaassasaysaaysaayaaaaysyaaaa";
        int respace = respace(dictionary,sentence);
        System.out.println(respace);
    }

    public static int respace(String[] dictionary, String sentence) {
        if (dictionary == null){
            return sentence.length();
        }
        int length = dictionary.length;
        if (length == 0){
            return sentence.length();
        }
        for(int i = 0;i<length-1;i++){
            for (int j=i+1;j<length;j++){
                String iString = dictionary[i];
                String jString = dictionary[j];
                if (iString.length() < jString.length()){
                    dictionary[i] = jString;
                    dictionary[j] = iString;

                }
            }
        }
        System.out.println(Arrays.toString(dictionary));
        for (String dic:dictionary){
            sentence = sentence.replaceAll(dic, "");
        }
        System.out.println(sentence);
        return sentence.length();
    }
}
